Beginners Guide to Code Algorithms Experiments to Enhance Productivity and Solve Problems (Deepankar Maitra)

Explore Your Deductive Logic—Sudoku

of this pattern is that 2 can be eliminated from all cells in rows 3, 5, and 7 except for

the corners of this pattern, marked with (2).

(2)

COLUMN 1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1

ROW

FIGURE 3.8 Polyomino.

The golden rectangle algorithm we discussed earlier has a step that identifies the

first 2 corners of the rectangle. We can utilize this logic to extend the concept of the

golden rectangle to a polyomino as shown above. If you recall, we start scanning

from the left, to search for a column that has exactly two candidates for a certain

“putnumber”. Once we find a column that meets this criterion, we keep looking for

more columns to the right that are similar. Then, we collect the row numbers for the

candidate cells in all the columns found. If three columns are found, then there are six

cells. If they contain only three unique row numbers, then this is a golden polyomino.

(Fun fact: in the example above, it is an enneadecamino because it is made up of 19

squares.) Similarly, if four columns are found, there are eight cells—if these eight

cells have only four unique row numbers, then this is also a golden polyomino. Note

that the golden rectangle is a specific example of this situation where there are only

two columns that meet this criterion and the four candidate cells have only three

unique rows.

The codes that follow are the three steps to examine the 9 by 9 grid for a polyomino,

collect the row numbers, and then use that information to update the relevant rows of

cells with the number.

Note that this code is to scan the matrix row by row for columns that have the same

possible number only in two out of nine rows. A similar piece of code is required to

examine the matrix column by column for rows that have the same possible number

only in two out of 9nine columns. This is a good exercise for you to solve.

Also, note also that the golden rectangle algorithm is a special case of a polyomino

hence no longer required separately if you are implementing the algorithm of the

polyomino.